//合并 K 个升序链表
/*给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
struct comp {
    bool operator()(ListNode* a, ListNode* b) { return a->val > b->val; }
};
class Solution {

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* head = new ListNode;
        ListNode* _head = head;
        priority_queue<ListNode*, vector<ListNode*>, comp> ret;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i])
                ret.push(lists[i]);
        }
        while (ret.size()) {
            ListNode* temp = ret.top();
            _head->next = temp;
            _head = _head->next;
            ret.pop();
            if (temp->next) {
                ret.push(temp->next);
            }
        }
        return head->next;
    }
};